package sort;

import org.junit.Test;

import java.util.Arrays;

public class Sort {
    @Test
    public void test1() {
        //冒泡排序
        //每次冒泡相邻数据对比，交换，结果是把最大的数字排到最后
        //需要冒泡n次，每次冒泡需要对比n次
        int[] list = new int[]{5, 3, 4, 1, 2};
        for (int i = 0; i < list.length; i++) {
            boolean flag = false;
            for (int j = 0; j < (list.length - i - 1); j++) {//已经排到最末尾的数据不用比较
                if (list[j] > list[j + 1]) {
                    int a = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = a;
                    flag = true;
                }
            }
            System.out.println(String.format("第%d次冒泡:%s", i + 1, Arrays.toString(list)));
            if (!flag) {
                break;//本次冒泡没有数据交换，提前退出
            }
        }
    }

    @Test
    public void test2() {
        //插入排序
        int[] list = new int[]{5, 3, 4, 1, 2};
        for (int i = 0; i < list.length; i++) {
            int a = list[i];
            int j = i - 1;
            for (; j >= 0; j--) {//遍历已排序的区域，比较大小后插入，插入后面的要后移，具体操作是先后移再插入
                if (list[j] > a) {
                    list[j + 1] = list[j];//后移
                } else {
                    break;
                }
            }
            list[j + 1] = a;//插入
            System.out.println(String.format("第%d次插入:%s", i + 1, Arrays.toString(list)));
        }
    }

    @Test
    public void test3() {
        //选择排序
        int[] list = new int[]{4, 5, 6, 3, 2, 1};
        for (int i = 0; i < list.length; i++) {
            int a = list[i];
            int min = i;
            for (int j = i; j < list.length; j++) {//找出未排序区的最小元素，交换到排序区的末尾
                if (list[j]  < list[min]){
                    min = j;
                }
            }
            if (min != i){
                list[i] = list[min];
                list[min] = a;
            }
            System.out.println(String.format("第%d次选择:%s", i + 1, Arrays.toString(list)));
        }
    }

    @Test
    public void test4() {
        //归并排序
        int[] list = new int[]{5, 3, 4, 1, 2, 6, 0};
        sort(list, 0, list.length - 1);
        System.out.println(String.format("排序后:%s", Arrays.toString(list)));
    }

    private void sort(int[] arr, int startIndex, int endIndex) {
        // 递归结束条件：startIndex大于等于endIndex的时候
        if (startIndex >= endIndex) {
            return;
        }
        // 折半递归
        int midIndex = (startIndex + endIndex) / 2;
        sort(arr, startIndex, midIndex);
        sort(arr, midIndex + 1, endIndex);
        // 将两个有序的小数组，合并成一个大数组
        merge(arr, startIndex, midIndex, endIndex);
    }

    private void merge(int[] arr, int startIndex, int midIndex, int endIndex) {
        // 新建一个大数组
        int[] tempArr = new int[arr.length];
        int p1 = startIndex;
        int p2 = midIndex + 1;
        int p = 0;
        // 比较两个有序小数组的元素，依次放入大数组中
        while (p1 <= midIndex && p2 <= endIndex) {
            if (arr[p1] <= arr[p2]) {
                tempArr[p++] = arr[p1++];
            } else {
                tempArr[p++] = arr[p2++];
            }
        }
        // 右侧小数组已排序完毕，左侧小数组还有剩余，将左侧小数组元素依次放入大数组尾部
        while (p1 <= midIndex) {
            tempArr[p++] = arr[p1++];
        }
        // 左侧小数组已排序完毕，右侧小数组还有剩余，将右侧小数组元素依次放入大数组尾部
        while (p2 <= endIndex) {
            tempArr[p++] = arr[p2++];
        }
        for (int i = 0; i < p; i++) {
            arr[i + startIndex] = tempArr[i];
        }
    }

}
